#include <iostream>
#include <stack>
using namespace std;

int largestRectangleArea(int heights[], int n){
    stack<int> stack;
    stack.push(-1);
    int maxArea = 0;
    for(int i = 0; i < n; i++){
        while(stack.top() != -1 && heights[i] <= heights[stack.top()]){
            int height = heights[stack.top()];
            stack.pop();
            int width = i - stack.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        stack.push(i);
    }
    while(stack.top() != -1){
        int height = heights[stack.top()];
        stack.pop();
        int width = n - stack.top() - 1;
        maxArea = max(maxArea, height * width);
    }
    return maxArea;
}

int main(){
    int heights[] = {3, 2, 5, 4, 6, 1, 4, 2};
    int res = largestRectangleArea(heights, 8);
    cout<<res<<endl;
    return 0;
}